# 有序集合
# class Solution(object):
#     def fallingSquares(self, positions):
#         """
#         :type positions: List[List[int]]
#         :rtype: List[int]
#         """
#         n = len(positions)
#         stack = [[positions[0][0], positions[0][0] + positions[0][1] - 1, positions[0][1]]]
#         out = [0] * n
#         out[0] = positions[0][1]
#
#         def find_left(start):
#             left = 0
#             right = len(stack) - 1
#             while left < right:
#                 mid = (left + right) // 2
#                 if start > stack[mid][1]:
#                     left = mid + 1
#                 else:
#                     right = mid
#             if stack[left][1] < start:
#                 return left + 1
#             else:
#                 return left
#
#         def find_right(end):
#             left = 0
#             right = len(stack) - 1
#             while left < right:
#                 mid = (left + right + 1) // 2
#                 if stack[mid][0] > end:
#                     right = mid - 1
#                 else:
#                     left = mid
#             if stack[left][0] <= end:
#                 return left
#             else:
#                 return left - 1
#
#         for i in range(1, n):
#             node = [positions[i][0], positions[i][0] + positions[i][1] - 1, positions[i][1]]
#             left = find_left(node[0])
#             right = find_right(node[1])
#             if left > right:
#                 stack.insert(left, node)
#                 out[i] = max(out[i - 1], node[2])
#             if left <= right:
#                 left_stack = stack[: left]
#                 right_stack = stack[right + 1:]
#                 max_val = max([stack[j][2] for j in range(left, right + 1)])
#                 node[2] += max_val
#                 out[i] = max(out[i - 1], node[2])
#                 if stack[left][0] < node[0]:
#                     left_stack.append([stack[left][0], node[0] - 1, stack[left][2]])
#                 if stack[right][1] > node[1]:
#                     right_stack.insert(0, [node[1] + 1, stack[right][1], stack[right][2]])
#                 stack = left_stack + [node] + right_stack
#         return out

# 线段树
class TreeNode():
    def __init__(self):
        self.left = self.right = None
        self.val = 0
        self.lazy = False

class Solution(object):
    def fallingSquares(self, positions):
        maxRange = 10 ** 8 + 10 ** 6
        tree = TreeNode()
        def down(node):
            if not node.left:
                node.left = TreeNode()
            if not node.right:
                node.right = TreeNode()
            if node.lazy:
                node.left.val = node.right.val = node.val
                node.lazy = False
                node.left.lazy = node.right.lazy = True


        def up(node):
            node.val = max(node.left.val, node.right.val)

        def update(node, ls, rs, l, r, h):
            if l <= ls and rs <= r:
                node.lazy = True
                node.val = h
            else:
                down(node)
                mid = (ls + rs) // 2
                if l <= mid:
                    update(node.left, ls, mid, l, r, h)
                if r >= mid + 1:
                    update(node.right, mid + 1, rs, l, r, h)
                up(node)

        def query(node, ls, rs, l, r):
            if l <= ls and rs <= r:
                return node.val
            else:
                down(node)
                mid = (ls + rs) // 2
                max_value = 0
                if l <= mid:
                    max_value = max(max_value, query(node.left, ls, mid, l, r))
                if r >= mid + 1:
                    max_value = max(max_value, query(node.right, mid + 1, rs, l, r))
                return max_value

        out = []
        for p in positions:
            left = p[0]
            right = p[0] + p[1] - 1
            h = query(tree, 0, maxRange, left, right) + p[1]
            update(tree, 0, maxRange, left, right, h)
            out.append(tree.val)
        return out







data = Solution()
positions = [[1, 2], [2, 3], [6, 1]]
print(data.fallingSquares(positions))
positions = [[1, 2], [3, 3], [2, 2], [8, 6], [3, 9]]
print(data.fallingSquares(positions))
positions = [[44, 98], [29, 95], [11, 22], [66, 39], [24, 45], [43, 29], [25, 45], [64, 47], [29, 81], [18, 1]]
print(data.fallingSquares(positions))
